package test.algorithm.FastSlowPointer;

/**
 * 约瑟夫环
 * @author serenity
 *
 */
public class Josephus {
	
	static class Node {
		private int num;
		private Node next;
		
		public Node(int num){
			this.num = num;
		}
	}
	
	/**
	 * 打印链表
	 * @param node
	 */
	static void printList(Node header){
		Node pointer = header.next;
		do{
			System.out.print(pointer.num+" ");
			pointer = pointer.next;
		}while(pointer!=null && pointer!=header.next);
		System.out.println();
	}

	public static void main(String[] args) {
		
		//头结点，声明一个链表（头结点值存储链表长度，不存储数据）
		Node header = new Josephus.Node(0);
		Node pointer = header;
		
		//初始化循环链表
		for(int i=1;i<=15;i++){
			pointer.next = new Josephus.Node(i);
			pointer = pointer.next;
			header.num = i;
		}
		pointer.next = header.next;
		printList(header);
		
		//自杀过程
		pointer = header.next;
		int i = 0;
		System.out.print("自杀顺序号：");
		//周期数
		int cycleNum = 3;
		// 如果链表长度大于等于周期数
		while(header.num>=cycleNum){
			i++;
			// 当i等于周期数-1时，即下一个号码就是要出列的号码
			// 为啥要周期数-1？因为该链表的节点只能找下一个
			if(i==(cycleNum-1)){
				// temp为要出列的号码
				Node temp = pointer.next;
				// 从链表中删除temp
				pointer.next = pointer.next.next;
				
				//如果删除的是链表的第一个节点，则header.next要指向第一个节点的next
				if(header.next==temp){
					header.next = temp.next;
				}
				// 链表长度更新
				header.num = header.num-1;
				// 已删除节点的next设置为空，方便垃圾回收
				// 防止已删除节点相互引用造成内存泄露
				temp.next = null;
				
				// 打印出列号码
				System.out.print(temp.num+" ");
				
				// 指针移动一位
				pointer = pointer.next;
				// 周期重新开始
				i=0;
			}else{
				pointer = pointer.next;
			}
		}
		
		//最后不够周期的两个号码，刚好是约瑟夫和他朋友的号码
		//他们不执行自杀规则的就不用死了
		System.out.println();
		System.out.print("幸存下来号码：");
		printList(header);
	}

}
